//给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i 
//+ 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。 
//
// 
//
// 示例 1： 
//
// 
//输入：arr = [3,1,3,6]
//输出：false
// 
//
// 示例 2： 
//
// 
//输入：arr = [2,1,2,6]
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：arr = [4,-2,2,-4]
//输出：true
//解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= arr.length <= 3 * 104 
// arr.length 是偶数 
// -105 <= arr[i] <= 105 
// 
// Related Topics 贪心 数组 哈希表 排序 
// 👍 145 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class ArrayOfDoubledPairs {
    public static void main(String[] args) {
        int[] arr = {-4, -2, 2, 4};
        new ArrayOfDoubledPairs().new Solution().canReorderDoubled(arr);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 以0为基准，以num的绝对值构建小顶堆
         * 每次取出x，如果x没有匹配过，那么x一定是匹配中的较小值，此时对2*x添加一次匹配记录
         * 如果x被匹配过了，说明x与之前的x/2组成了数对，将x计数次数--
         */
        int N = 100010;
        int M = 2 * N;
        int[] cnts = new int[2 * M];
        public boolean canReorderDoubled1(int[] arr) {
            PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Math.abs(a) - Math.abs(b));
            for (int num : arr) queue.offer(num);
            while (!queue.isEmpty()){
                int num = queue.poll(), t = 2 * num;
                // 如果num匹配过了，那么先对匹配值-1，如果num记录-1之后<0了，说明num成了小值，需要记录2倍值
                if (cnts[num + M] != 0 && --cnts[num + M] >= 0) continue;
                cnts[t + M]++;// 此时num是数对中较小的一个
            }
            for (int cnt : cnts) if (cnt != 0) return false;
            return true;
        }

        /**
         * 使用cnt数组进行计数，使用list保存元素顺序
         * 遍历list中的元素进行验证
         * 这个最好理解，也很快
         */
        public boolean canReorderDoubled2(int[] arr) {
            List<Integer> list = new ArrayList<>();
            for (int num : arr) {
                if (++cnts[num + M] == 1) list.add(num);// 保留元素
            }
            list.sort((a, b) -> Math.abs(a) - Math.abs(b));// 按照绝对值大小进行排序
            for (Integer num : list){
                if (cnts[2 * num + M] < cnts[num + M]) return false;// 从小到大进行验证，如果都验证通过就满足要求
                cnts[num * 2 + M] -= cnts[num + M];// 减去次数
            }
            return true;
        }

        /**
         * 拓扑排序+计数
         * 使用in[]数组记录节点入度，入度为0的话加入队列
         * 为了防止成环，需要对0进行预处理
         */
        int[] in = new int[2 * M];
        public boolean canReorderDoubled3(int[] arr) {
            List<Integer> list = new ArrayList<>();
            for (int num : arr){
                if (++cnts[num + M] == 1 && num != 0) list.add(num);// 计数并记录
            }
            if (cnts[M] % 2 != 0) return false;// 处理0
            list.sort((a, b) -> Math.abs(a) - Math.abs(b));
            Deque<Integer> deque = new ArrayDeque<>();// 保存入度为0的数
            for (int num : list){
                if (num % 2 == 0){// 说明num可以为入也可以为出
                    in[num + M] = cnts[num / 2 + M];// 设置当前节点的入度
                    if (in[num + M] == 0) deque.addLast(num);// 此时说明num入度为0
                }else deque.addLast(num);// 奇数入度都是0
            }
            while (!deque.isEmpty()){
                int t = deque.pollFirst();
                if (cnts[2 * t + M] < cnts[t + M]) return false;
                cnts[2 * t + M] -= cnts[t + M];
                in[2 * t + M] -= cnts[t + M];
                // 如果大数入度减小到0就需要入队列了
                if (in[2 * t + M] == 0 && cnts[2 * t + M] != 0) deque.addLast(2 * t);
                // 减小2*t数量之后需要同时修改4 * t的入度
                in[4 * t + M] -= cnts[t + M];
                // 入度为0之后也需要加入队列
                if (in[4 * t + M] == 0 && cnts[4 * t + M] != 0) deque.addLast(4 * t);
            }
            return true;
        }


        /**
         * 只使用小顶堆，按照绝对值保存所有元素，然后每次取最小的那个
         * 这个是真的慢
         */
        public boolean canReorderDoubled(int[] arr) {
            PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Math.abs(a) - Math.abs(b));
            for (int num : arr) queue.add(num);
            while (!queue.isEmpty()) {
                int num = queue.poll();
                if (!queue.contains(2 * num)) return false;// 不存在就不行
                queue.remove(2 * num);// 存在就去除一个
            }
            return true;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)
}































